package org.example;

import java.util.LinkedList;
import java.util.Queue;

// 序列化和反序列化
// https://labuladong.online/algo/data-structure/serialize-and-deserialize-binary-tree/
// 总结下结论，当二叉树中节点的值不存在重复时：
// 如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
// 如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文
// 二叉树心法（构造篇） 所说，分两种情况：
// 2.1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
// 2.2. 如果你给出前序和后序，那么你无法还原出唯一的一棵二叉树。
// 如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
// 3.1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
// 3.2. 如果你给出的是中序，那么你无法还原出唯一的一棵二叉树。
public class BinaryTree3 {
    // 297. 二叉树的序列化与反序列化
    // 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
    // 同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
    //
    //请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
    // 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

    // 【前序遍历解法】
    static class Codec1{

        // 代表分隔符的字符
        String SEP = ",";

        // 代表null空指针的字符
        String NULL = "#";

        // 序列化(主函数，将二叉树序列化为字符串)
        public String serialize(TreeNode root) {
            // 用于拼接字符串
            StringBuilder sb = new StringBuilder();
            _serialize(root, sb);
            return sb.toString();
        }

        // 辅助函数，将二叉树存入StringBuilder
        void _serialize(TreeNode root, StringBuilder sb){
            if (root == null){
                sb.append(NULL).append(SEP);
                return;
            }
            // ************前序位置***********
            sb.append(root.val).append(SEP);
            // ******************************
            _serialize(root.left, sb);
            _serialize(root.right, sb);
        }

        // 前文 二叉树心法（构造篇） 说过，至少要得到前、中、后序遍历中的两种互相配合才能还原二叉树。那是因为前文的遍历结果没有记录空指针的信息。
        // 这里的 nodes 列表包含了空指针的信息，所以只使用 nodes 列表就可以还原二叉树。

        // 反序列化(那么，反序列化过程也是一样，先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树即可：)
        // 主函数，将字符串反序列化为二叉树结构
        public TreeNode deserialize(String data) {
            // 将字符串转化成列表
            LinkedList<String> nodes = new LinkedList<>();
            for(String s : data.split(SEP)){
                nodes.addLast(s);
            }
            return _deserialize(nodes);
        }

        // 辅助函数，通过 nodes 列表构造二叉树
        TreeNode _deserialize(LinkedList<String> nodes){
            if (nodes.isEmpty()){
                return null;
            }
            // ****** 前序位置 ********
            // 列表最左侧就是根节点
            String first = nodes.removeFirst();
            if (first.equals(NULL)){
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(first));
            // *********************

            root.left = _deserialize(nodes);
            root.right = _deserialize(nodes);
            return root;
            // 我们发现，根据树的递归性质，nodes 列表的第一个元素就是一棵树的根节点，
            // 所以只要将列表的第一个元素取出作为根节点，剩下的交给递归函数去解决即可。
        }
    }

    // 【后序遍历解法】
    static class Codec2{
        String SEP = ",";
        String NULL = "#";

        // 主函数，将二叉树序列化为字符串
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            _serialize(root, sb);
            return sb.toString();
        }

        void _serialize(TreeNode root, StringBuilder sb){
            if (root == null){
                sb.append(NULL).append(SEP);
                return;
            }
            _serialize(root.left, sb);
            _serialize(root.right, sb);

            // ****** 后序位置 ********
            sb.append(root.val).append(SEP);
            // ***********************
        }

        // 主函数，将字符串反序列化为二叉树结构
        public TreeNode deserialize(String data) {
            LinkedList<String> nodes = new LinkedList<>();
            for(String s : data.split(SEP)){
                nodes.addLast(s);
            }
            return _deserialize(nodes);
        }

        // 辅助函数，通过 nodes 列表构造二叉树
        TreeNode _deserialize(LinkedList<String> nodes){
            if (nodes.isEmpty()){
                return null;
            }
            // 从后往前取出元素
            String last = nodes.removeLast();
            if (last.equals(NULL)){
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(last));
            // 先构造右子树，后构造左子树
            root.right = _deserialize(nodes);
            root.left = _deserialize(nodes);
            return root;
        }
    }

    // 【中序遍历解法】
    // 先说结论，中序遍历的方式行不通，因为无法实现反序列化方法 deserialize。
    // 序列化方法 serialize 依然容易，只要把辅助函数 _serialize 中的字符串的拼接操作放到中序遍历的位置就行了：
    static class Codec3{
        String SEP = ",";
        String NULL = "#";
        // 辅助函数，将二叉树存入 StringBuilder
        void serialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append(NULL).append(SEP);
                return;
            }

            serialize(root.left, sb);
            // ****** 中序位置 ******
            sb.append(root.val).append(SEP);
            // *********************
            serialize(root.right, sb);
        }
        // 但是，我们刚才说了，要想实现反序列方法，首先要构造 root 节点。
        // 前序遍历得到的 nodes 列表中，第一个元素是 root 节点的值；后序遍历得到的 nodes 列表中，最后一个元素是 root 节点的值。
        // 你看上面这段中序遍历的代码，root 的值被夹在两棵子树的中间，也就是在 nodes 列表的中间，我们不知道确切的索引位置，
        // 所以无法找到 root 节点，也就无法进行反序列化。
    }

    // 【层序遍历解法】
    static class Codec4{

        // 标准的二叉树的层序遍历
        void traverse(TreeNode root){
            if (root == null){
                return;
            }
            // 初始化队列，将root加入到队列
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);

            while(!q.isEmpty()){
                int sz = q.size();
                for(int i = 0; i < sz; i++){
                    // 层级遍历代码位置
                    TreeNode cur = q.poll();
                    System.out.println(cur.val);
                    // ***************

                    if (cur.left != null){
                        q.offer(cur.left);
                    }
                    if (cur.right != null){
                        q.offer(cur.right);
                    }
                }
            }
        }
        // 上述代码是标准的二叉树层级遍历框架，从上到下，从左到右打印每一层二叉树节点的值，可以看到，队列 q 中不会存在 null 指针。

        // 不过我们在反序列化的过程中是需要记录空指针 null 的，所以可以把标准的层级遍历框架略作修改：

        void traverse1(TreeNode root){
            if (root == null){
                return;
            }
            // 初始化队列，将root加入到队列
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);

            while(!q.isEmpty()){
                int sz = q.size();
                for(int i = 0; i < sz; i++){
                    TreeNode cur = q.poll();
                    // 层级遍历代码位置
                    if (cur == null){
                        continue;
                    }
                    System.out.println(cur.val);
                    // ***************
                    q.offer(cur.left);
                    q.offer(cur.right);
                }
            }
        }

        String SEP = ",";
        String NULL = "#";

        // 将二叉树序列化为字符串
        public String serialize(TreeNode root){
            if (root == null){
                return "";
            }
            StringBuilder sb = new StringBuilder();
            // 初始化队列，将root加入队列
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);

            while(!q.isEmpty()){
                int sz = q.size();
                for(int i = 0; i < sz; i++){
                    TreeNode cur = q.poll();
                    // 层级遍历代码位置
                    if (cur == null){
                        sb.append(NULL).append(SEP);
                        continue;
                    }
                    sb.append(cur.val).append(SEP);
                    // ********************************
                    q.offer(cur.left);
                    q.offer(cur.right);
                }
            }
            return sb.toString();
        }


        // 将字符串反序列化为二叉树结构
        public TreeNode deserialize(String data) {
            if (data.isEmpty()){
                return null;
            }
            String[] nodes = data.split(SEP);
            // 第一个元素就是root的值
            TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
            // 队列q记录父节点，将root加入队列
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);

            // index变量记录正在序列化的节点在数组中的位置
            int index = 1;
            while(!q.isEmpty()){
                int sz = q.size();
                for(int i = 0; i < sz; i++){
                    TreeNode parent = q.poll();
                    // 为父节点构造左侧子节点
                    String left = nodes[index++];
                    if (!left.equals(NULL)){
                        parent.left = new TreeNode(Integer.parseInt(left));
                        q.offer(parent.left);
                    }
                    // 为父节点构造右侧子节点
                    String right = nodes[index++];
                    if (!right.equals(NULL)){
                        parent.right = new TreeNode(Integer.parseInt(right));
                        q.offer(parent.right);
                    }
                }
            }
            return root;
        }
    }

}
